package com.shm.leetcode;

/**
 * 3. 秋叶收藏集
 * 题目难度 Medium
 * 小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。
 * 出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
 * <p>
 * 示例 1：
 * <p>
 * 输入：leaves = "rrryyyrryyyrr"
 * <p>
 * 输出：2
 * <p>
 * 解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"
 * <p>
 * 示例 2：
 * <p>
 * 输入：leaves = "ryr"
 * <p>
 * 输出：0
 * <p>
 * 解释：已符合要求，不需要额外操作
 * <p>
 * 提示：
 * <p>
 * 3 <= leaves.length <= 10^5
 * leaves 中只包含字符 'r' 和字符 'y'
 *
 * @author SHM
 */
public class MinimumOperations {
    /**
     * 用 sum[x] 表示 [0, x) 区间内红叶数量. 假设整理后红叶的区间为 [0, i) 和 [j, n), 那么黄叶区间为 [i, j).
     *
     * 对于左右两个区间, 操作次数为区间长度减去红叶的数量, 对于中间的区间, 操作次数就是红叶的数量.
     *
     * 需要操作的总次数为 (i - sum[i]) + (n - j - sum[n] + sum[j]) + (sum[j] - sum[i]), 整理后得到 n - sum[n] + (i - 2 * sum[i]) - (j - 2 * sum[j]), 约束条件为 0 < i < j < n. 为了让操作数最少, 我们希望 j 确定时 i - 2 * sum[i] 最小.
     *
     * 用 min[x] 记录 [1, x] 区间内的 i - 2 * sum[i] 的最小值, 将 j 从 n - 1 遍历到 2, min[j - 1] 即为当前最小的 i - 2 * sum[i].
     *
     * 作者：aerysn
     * 链接：https://leetcode-cn.com/problems/UlBDOe/solution/simple-java-by-aerysn/
     * @param leaves
     * @return
     */
    public int minimumOperations(String leaves) {
        int n = leaves.length();
        char[] chars = leaves.toCharArray();
        int[] sum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + (chars[i] == 'r' ? 1 : 0);
        }
        int[] min = new int[n + 1];
        int currMin = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) {
            currMin = Math.min(currMin, i - 2 * sum[i]);
            min[i] = currMin;
        }
        int result = Integer.MAX_VALUE;
        for (int j = n - 1; j > 1; j--) {
            result = Math.min(result, n - sum[n] + min[j - 1] - j + 2 * sum[j]);
        }
        return result;
    }

    /**
     * 方法一：动态规划
     * 思路与算法
     *
     * 由于我们想要将收藏集中树叶的排列调整成「红、黄、红」三部分，因此我们可以用 33 个状态分别表示其中的每一部分，即状态 00 和状态 22 分别表示前面和后面的红色部分，状态 11 表示黄色部分。
     *
     * 此时，我们就可以尝试使用动态规划解决本题了。我们用 f[i][j]f[i][j] 表示对于第 00 片到第 ii 片叶子（记为 \textit{leaves}[0..i]leaves[0..i]）进行调整操作，并且第 ii 片叶子处于状态 jj 时的最小操作次数。在推导状态转移方程时，我们可以分别对于每一种状态进行分析。
     *
     * 当 j=0j=0 时，我们需要将第 ii 片叶子变成红色，并且第 i-1i−1 片叶子也只能处于 j=0j=0 的状态（因为没有编号更小的状态了），因此有状态转移方程：
     *
     * f[i][0] = f[i-1][0] + \text{isYellow}(i)
     * f[i][0]=f[i−1][0]+isYellow(i)
     *
     * 其中 \text{isYellow}(i)isYellow(i) 为示性函数，当第 ii 片叶子为黄色时为 11，红色时为 00。
     *
     * 当 j=1j=1 时，我们需要将第 ii 片叶子变成黄色，而第 i-1i−1 片叶子既可以处于 j=1j=1 的状态，也可以处于 j=0j=0 的状态，我们选择其中的较小值，因此有状态转移方程：
     *
     * f[i][1] = \min \{ f[i-1][0], f[i-1][1] \} + \text{isRed}(i)
     * f[i][1]=min{f[i−1][0],f[i−1][1]}+isRed(i)
     *
     * 其中 \text{isRed}(i)isRed(i) 为示性函数，当第 ii 片叶子为红色时为 11，黄色时为 00。
     *
     * 当 j=2j=2 时，我们需要将第 ii 片叶子变成红色，而第 i-1i−1 片叶子即可以处于 j=2j=2 的状态，也可以处于 j=1j=1 的状态（注意这里不能处于 j=0j=0 的状态，因为每一种状态包含的叶子数量必须至少为 11），我们选择其中的较小值，因此有状态转移方程：
     *
     * f[i][2] = \min \{ f[i-1][1], f[i-1][2] \} + \text{isYellow}(i)
     * f[i][2]=min{f[i−1][1],f[i−1][2]}+isYellow(i)
     *
     * 最终的答案即为 f[n-1][2]f[n−1][2]，其中 nn 是字符串 \textit{leaves}leaves 的长度，也就是树叶的总数。
     *
     * 细节
     *
     * 由于 因为每一种状态包含的叶子数量必须至少为 11，因此不仅需要特别注意 j=2j=2 时的状态转移方程，还需要考虑每个状态本身是否是符合要求的。对于状态 f[i][j]f[i][j] 而言，它包含了 \textit{leaves}[0..i]leaves[0..i] 共 i+1i+1 片叶子以及 j+1j+1 个状态，因此 叶子的数量必须大于等于状态的数量，即满足 i \geq ji≥j。这样一来，所有 i < ji<j 的状态 f[i][j]f[i][j] 都是不符合要求的。观察上面的状态转移方程，我们在每一步转移时都是取最小值，因此我们可以将所有不符合要求的状态置为一个极大值（例如 n+1n+1 或整数类型的上限等）。
     *
     * 同时需要注意的是，当 i=0i=0 时，f[i][..]f[i][..] 会从 f[i-1][..]f[i−1][..] 转移而来，但后者是没有意义的，因此我们需要对 f[i][..]f[i][..] 进行特殊处理。由于当 i=0i=0 时，jj 也只能为 00，因此我们有：
     *
     * f[0][0] = \text{isYellow}(0)
     * f[0][0]=isYellow(0)
     *
     * 作为唯一的边界条件。
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是字符串 \textit{leaves}leaves 的长度。
     *
     * 空间复杂度：O(n)O(n)。
     *
     * 可以使用「降维」优化，用三个变量代替状态数组，即可将空间复杂度降低到 O(1)O(1)。具体操作留给读者自行实现。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/UlBDOe/solution/qiu-xie-shou-cang-ji-by-leetcode-solution/
     * @param leaves
     * @return
     */
    public int minimumOperations_2(String leaves) {
        int n = leaves.length();
        /*
            状态数组，state[i][j]中：
                i表示终止下标
                j表示：0为左半边，1为中间部分，2为右半边
            state[i][j] 表示 从0到i需要调整的叶子数
         */

//        作者：leetcoder-youzg
//        链接：https://leetcode-cn.com/problems/UlBDOe/solution/java-quan-zhu-shi-li-jie-dong-tai-gui-hua-by-leetc/
        int[][] f = new int[n][3];
        /*
            记录 已知状态数组元素：
                1、第一个叶子，必须是左半部分，所以只需判断是不是 黄色叶子 即可
                2、第一个叶子，必须是左半部分，所以 state[0][1] 和 state[0][2] 都是无效的
                3、第二个叶子，可以是左半部分，也可以是中间部分，但是不能是右半部分(每个区间必须有叶子)，
                    因此 state[1][2]是无效的
         */
        f[0][0] = leaves.charAt(0)=='y'?1:0;
        f[0][1]=f[0][2]=f[1][2]=Integer.MAX_VALUE;
        /*
            遍历 原叶集，生成状态数组
         */
        for (int i = 1; i < n; i++) {
            int isRed = leaves.charAt(i)=='r'?1:0;
            int isYellow = leaves.charAt(i)=='y'?1:0;
            f[i][0]=f[i-1][0]+isYellow;
            f[i][1]=Math.min(f[i-1][0],f[i-1][1])+isRed;
            // 右半部分 的叶子 必须是第2个元素之后的元素
            if (i>=2){
                f[i][2]=Math.min(f[i-1][1],f[i-1][2])+isYellow;
            }
        }
        return f[n-1][2];
    }
}
